#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
"""

class Solution:
    """
    @param nums: An integer array
    @return: The length of LIS (longest increasing subsequence)
    """
    def longestIncreasingSubsequence(self, nums):
        if not nums:
            return 0

        self.nums = nums
        l = len(nums)
        self.local_nums = [1] * l
        global_num = 1

        for i in range(1, l):
            local_cur = self.get_local(i)
            self.local_nums[i] = local_cur
            global_num = max(global_num, local_cur)

        return global_num

    def get_local(self, idx):
        local_cur = 1

        for i in range(0, idx):
            if self.nums[idx] > self.nums[i]:
                local_cur = max(local_cur, self.local_nums[i] + 1)

        return local_cur


def main():
    print("start main")
    s = Solution()
    l = [5, 4, 1, 2, 3]
    l = [4, 2, 4, 5, 3, 7]
    ret = s.longestIncreasingSubsequence(l)
    print(ret)

if __name__ == "__main__":
    main()
